The present invention relates to a content addressable memory suitable for use with redundant form input signals.
It is a goal of memory systems to fulfill requests for stored data with as little delay as possible. Often, the requesting agent cannot achieve forward progress without the requested information. This principle holds true for content addressable memories (xe2x80x9cCAMsxe2x80x9d).
However, increasingly, arithmetic operations are included as part of a memory operation. That is, a request for data defines one or more arithmetic operations whose result is to be applied to a memory as an address. Any time spent completing an arithmetic operation is delay introduced to a memory request that includes the arithmetic operation. Thus, it becomes a goal of memory systems to reduce the time required to perform any arithmetic operations included in a memory request.
FIG. 1 illustrates a traditional adder circuit. There, an addition performed on two multi-bit values X (X=X0xe2x88x92X3) and Y (Y=Y0xe2x88x92Y3) generates a multi-bit sum S (S=S0xe2x88x92S3) and a carry out Cout. The traditional adder includes an internal carry chain wherein a carry from a first bit position i may affect the value of the sum at a second bit position i+1. Carries must propagate through the entire length of the adder before true results may be obtained therefrom. The internal carry chain causes the traditional adder to be slow. There is a need in the art for a memory system that improves the processing speed of memory requests that require mathematical preprocessing operations.
Redundant form adders are known to be faster than traditional adders. Shown in FIG. 2, a redundant form adder omits the internal carry chain that characterizes the traditional adder. Instead, for each bit position i of inputs X, Y and Z, the redundant form adder generates a multi-bit sum Ŝi. The output Ŝ (Ŝ=Ŝ0xe2x88x92Ŝn) is said to be in xe2x80x9credundant formxe2x80x9d because two bits are used per bit position rather than a single bit to represent a sum result that may be more efficiently represented by only a single bit. To reduce the redundant form result Ŝ to non-redundant form, the two bits of each xe2x80x9cbit positionxe2x80x9d Ŝi may be input to a traditional adder, such as the adder of FIG. 1.
The redundant form adder provides significant processing advantages over traditional adder, particularly where a number of additions are performed in sequence. For a plural number of sequential adds, the traditional adder must complete the carry chain of each add before it may begin a subsequent add. However, redundant form processing permits quick additions to be performed. A carry chain may be omitted until a redundant form sum is obtained from the final addition. When the redundant form sum is obtained, it may be converted to non-redundant form by use of only a single carry chain.
No known memory system retrieves data based on redundant form input data.
Content addressable memories are known per se. A block diagram of a known CAM 100 is shown in FIG. 3. The CAM 100 includes a plurality of registers 110 each of which stores data. When input data is applied to the CAM 100, it generates an output identifying which registers, if any, store data having the same value as the input data. Typically, the CAM 110 generates an output signal having a one-bit flag per register position in the CAM. For example, the flag may be enabled if the register stores data that is equal to the input signal and disabled otherwise.
The CAM 100 contains match logic 120 associated with each register 110. The match logic 120 performs a bit-by-bit comparison of the input data and the data stored in the register 110. As shown in FIG. 4, it includes selection switches 130-160, one provided for each bit position C0-C3 of data in the register 110. Each switch 130-160 is controlled by the value of the associated bit position in the register 110. The output of each selection switch 130-160 is input to an AND gate 170.
Typically, for each bit position Di in the input signal, the match logic generates its complement, Di# (not shown). Di and Di# are input to the switch associated with register it position i. The value of the data stored in the register at bit position i controls which of Di and Di# are output to the AND gate 170 from the switch.
The AND gate 170 generates a signal representing a logical AND of the values output from each of the selection switches 130-160. The AND is a logical 1 only when the signal input to the CAM 100 has the same value as the data stored in the register 110.
No known memory system operates on redundant form input data. Accordingly, there is a need in the art for a content addressable memory system that reduces latency of memory requests when those requests include arithmetic operations. Further, there is a need in the art for a content addressable memory that operates on redundant form input data.
Embodiments of the present invention provide a content addressable memory addressable by redundant form input data.